package top.zz;

import com.sun.org.apache.regexp.internal.recompile;

/**
 * 二叉树
 * 
 * @author game
 *
 */

class Node {
	private int data; // 节点数据
	private Node leftChild; // 左子节点的引用
	private Node rightChild; // 右子节点的引用
	boolean isDelete;// 表示节点是否被删除

	public Node(int data) {
		this.data = data;
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public Node getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(Node leftChild) {
		this.leftChild = leftChild;
	}

	public Node getRightChild() {
		return rightChild;
	}

	public void setRightChild(Node rightChild) {
		this.rightChild = rightChild;
	}

	public boolean isDelete() {
		return isDelete;
	}

	public void setDelete(boolean isDelete) {
		this.isDelete = isDelete;
	}

	// 打印节点内容
	public void display() {
		System.out.println(data);
	}

}

interface Tree {
	/**
	 * 查找节点
	 * 
	 * @param key
	 * @return
	 */
	public Node find(int key);

	/**
	 * 插入新节点
	 * 
	 * @param data
	 * @return
	 */
	public boolean insert(int data);

	/**
	 * 中序遍历
	 * 
	 * 左 =》 根 =》 右
	 * 
	 * @param current
	 */
	public void infixOrder(Node current);

	/**
	 * 前序遍历
	 * 
	 * 根 =》 左 =》 右
	 * 
	 * @param current
	 */
	public void preOrder(Node current);

	/**
	 * 后序遍历
	 * 
	 * 左 =》 右 =》 根
	 * 
	 * @param current
	 */
	public void postOrder(Node current);

	/**
	 * 查找最大值
	 * 
	 * @return
	 */
	public Node findMax();

	/**
	 * 查找最小值
	 * 
	 * @return
	 */
	public Node findMin();

	/**
	 * 删除节点
	 * 
	 * @param key
	 * @return
	 */
	public boolean delete(int key);

}

class BinaryTree implements Tree {

	private Node root;

	@Override
	public Node find(int key) {

		Node current = root;

		while (current != null) {
			if (current.getData() > key) {
				current = current.getLeftChild();
			} else if (current.getData() < key) {
				current = current.getRightChild();
			} else {
				return current;
			}
		}

		return null;
	}

	@Override
	public boolean insert(int data) {
		Node node = new Node(data);
		if (root == null) {
			root = node;
			return true;
		} else {
			Node current = root;
			Node parent = null;

			while (current != null) {
				parent = current;

				if (current.getData() > data) {
					current = current.getLeftChild();
					if (current == null) {
						parent.setLeftChild(node);
						return true;
					}
				} else {
					current = current.getRightChild();
					if (current == null) {
						parent.setLeftChild(node);
						return true;
					}
				}

			}
		}
		return false;
	}

	@Override
	public void infixOrder(Node current) {
		if (current != null) {
			infixOrder(current.getLeftChild());
			System.out.println(current.getData());
			infixOrder(current.getRightChild());
		}

	}

	@Override
	public void preOrder(Node current) {
		if (current != null) {
			System.out.println(current.getData());
			preOrder(current.getLeftChild());
			preOrder(current.getRightChild());
		}

	}

	@Override
	public void postOrder(Node current) {
		if (current != null) {
			postOrder(current.getLeftChild());
			postOrder(current.getRightChild());
			System.out.println(current.getData());
		}

	}

	@Override
	public Node findMax() {
		Node current = root;

		while (current != null) {
			if (current.getRightChild() != null) {
				current = current.getRightChild();
			} else {
				return current;
			}
		}

		return null;
	}

	@Override
	public Node findMin() {
		Node current = root;

		while (current != null) {
			if (current.getLeftChild() != null) {
				current = current.getLeftChild();
			} else {
				return current;
			}
		}

		return null;
	}

	@Override
	public boolean delete(int key) {
		//操作数据的必要性
		Node current = find(key);
		if(current !=null) {
			current.setDelete(true);
			return true;
		}
		return false;
	}

}

public class BinaryTreeTest {

}
